package org.arclib.x.light;

import java.util.ArrayList;

import org.arclib.math.Point;

public class ConvexPolygon
{
	// / constructs from a vertex list, vertices must be in ccw order
	public static ConvexPolygon fromVertices(ArrayList<Point> verts)
	{
		ConvexPolygon poly = new ConvexPolygon();
		for (int i = 1; i < verts.size(); ++i)
			poly.edges.add(new Edge(verts.get(i - 1), verts.get(i)));
		poly.edges.add(new Edge(verts.get(verts.size() - 1), verts.get(0)));

		assert (poly.isValid());
		return poly;
	}

	// / edges, in ccw order
	ArrayList<Edge> edges;

	/***
	 * Finds the edges that face away from a given location 'from'.
	 * 
	 * Returns: A list of indices into 'edges'. In ccw order.
	 */
	public ArrayList<Integer> getBackfacingEdgeIndices(Point from)
	{
		assert (isValid());

		ArrayList<Integer> result = new ArrayList<Integer>();

		// find the indices of the two edges that face away from 'from' and that
		// have one adjacent edge facing towards 'from'
		int firstbackfacing = java.lang.Integer.MAX_VALUE;
		int lastbackfacing = java.lang.Integer.MAX_VALUE;

		{
			boolean prev_edge_front = false, cur_edge_front = false;
			for (int i = 0; i < edges.size(); i++)
			{
				if (edges.get(i).normal().dot(from.sub(edges.get(i).from)) < 0)
					cur_edge_front = true;
				else
					cur_edge_front = false;

				if (i != 0)
				{
					if (cur_edge_front && !prev_edge_front)
						firstbackfacing = i;
					else if (!cur_edge_front && prev_edge_front)
						lastbackfacing = i - 1;
				}

				prev_edge_front = cur_edge_front;
			}
		}

		// if no change between front and backfacing vertices was found,
		// we are inside the polygon, consequently all edges face backwards
		if (firstbackfacing == Integer.MAX_VALUE
				&& lastbackfacing == Integer.MAX_VALUE)
		{
			for (int i = 0; i < edges.size(); ++i)
				result.add(i);
			return result;
		}
		// else, if one one of the changes was found, we missed the one at 0
		else if (firstbackfacing == Integer.MAX_VALUE)
			firstbackfacing = 0;
		else if (lastbackfacing == Integer.MAX_VALUE)
			lastbackfacing = edges.size() - 1;

		// if this is true, we can just put the indices in result in order
		if (firstbackfacing <= lastbackfacing)
		{
			for (int i = firstbackfacing; i <= lastbackfacing; ++i)
				result.add(i);
		}
		// else we must go from first to $ and from 0 to last
		else
		{
			for (int i = firstbackfacing; i < edges.size(); ++i)
				result.add(i);
			for (int i = 0; i <= lastbackfacing; ++i)
				result.add(i);
		}

		return result;
	}

	// / returns true if the edges list makes up a convex polygon and are in ccw
	// order
	boolean isValid()
	{
		for (int i = 0; i < edges.size(); ++i)
		{
			int nexti = i + 1 < edges.size() ? i + 1 : 0;
			if (edges.get(i).to != edges.get(nexti).from)
				return false;
			if (edges.get(i).tangent().cross(edges.get(nexti).tangent()) <= 0)
				return false;
		}

		return true;
	}
}
